package leetcode.median;

import leetcode.base.TreeNode;

import java.util.Arrays;

/**
 * ClassName: $654_ConstructMaximumBinaryTree
 * Description: 最大二叉树
 * date: 2021-12-01 22:17
 *
 * @author liyifan
 */
public class $654_ConstructMaximumBinaryTree {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if (nums.length == 0)
            return null;
        if (nums.length == 1)
            return new TreeNode(nums[0]);
        return recur(nums, 0, nums.length - 1);
    }

    public TreeNode recur(int[] nums, int low, int high) {
        if (low == high) {
            return new TreeNode(nums[low]);
        }
        if (low > high)
            return null;

        int maxIndex = maxIndex(nums, low, high);
        TreeNode root = new TreeNode(nums[maxIndex]);
        root.left = recur(nums, low, maxIndex - 1);
        root.right = recur(nums, maxIndex + 1, high);
        return root;

    }

    public int maxIndex(int[] nums, int low, int high) {
        int max = nums[low];
        int maxIndex = low;
        for (int i = low;i <= high;i++) {
            if (nums[i] > max) {
                max = nums[i];
                maxIndex = i;
            }
        }
        return maxIndex;
    }
}
